home *** CD-ROM | disk | FTP | other *** search
/ MacFormat 1995 July / macformat-026.iso / mac / Shareware City / Developers / berkeleydb1.73 / Berkeley_db / btree / bt_seq.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-07-27  |  9.7 KB  |  385 lines  |  [TEXT/MPS ]
  1. /*-
  2.  * Copyright (c) 1990, 1993
  3.  *    The Regents of the University of California.  All rights reserved.
  4.  *
  5.  * This code is derived from software contributed to Berkeley by
  6.  * Mike Olson.
  7.  *
  8.  * Redistribution and use in source and binary forms, with or without
  9.  * modification, are permitted provided that the following conditions
  10.  * are met:
  11.  * 1. Redistributions of source code must retain the above copyright
  12.  *    notice, this list of conditions and the following disclaimer.
  13.  * 2. Redistributions in binary form must reproduce the above copyright
  14.  *    notice, this list of conditions and the following disclaimer in the
  15.  *    documentation and/or other materials provided with the distribution.
  16.  * 3. All advertising materials mentioning features or use of this software
  17.  *    must display the following acknowledgement:
  18.  *    This product includes software developed by the University of
  19.  *    California, Berkeley and its contributors.
  20.  * 4. Neither the name of the University nor the names of its contributors
  21.  *    may be used to endorse or promote products derived from this software
  22.  *    without specific prior written permission.
  23.  *
  24.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  25.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  28.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  30.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  31.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  33.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34.  * SUCH DAMAGE.
  35.  */
  36.  
  37. #if defined(LIBC_SCCS) && !defined(lint)
  38. static char sccsid[] = "@(#)bt_seq.c    8.2 (Berkeley) 9/7/93";
  39. #endif /* LIBC_SCCS and not lint */
  40.  
  41. #if defined(macintosh) && (defined(powerc) || defined(__powerc))
  42. #include "OurMalloc.h"
  43. #endif
  44.  
  45. #include <sys/types.h>
  46.  
  47. #include <errno.h>
  48. #include <stddef.h>
  49. #include <stdio.h>
  50. #include <stdlib.h>
  51.  
  52. #include <db.h>
  53. #include "btree.h"
  54.  
  55. static int     bt_seqadv __P((BTREE *, EPG *, int));
  56. static int     bt_seqset __P((BTREE *, EPG *, DBT *, int));
  57.  
  58. /*
  59.  * Sequential scan support.
  60.  *
  61.  * The tree can be scanned sequentially, starting from either end of the tree
  62.  * or from any specific key.  A scan request before any scanning is done is
  63.  * initialized as starting from the least node.
  64.  *
  65.  * Each tree has an EPGNO which has the current position of the cursor.  The
  66.  * cursor has to survive deletions/insertions in the tree without losing its
  67.  * position.  This is done by noting deletions without doing them, and then
  68.  * doing them when the cursor moves (or the tree is closed).
  69.  */
  70.  
  71. /*
  72.  * __BT_SEQ -- Btree sequential scan interface.
  73.  *
  74.  * Parameters:
  75.  *    dbp:    pointer to access method
  76.  *    key:    key for positioning and return value
  77.  *    data:    data return value
  78.  *    flags:    R_CURSOR, R_FIRST, R_LAST, R_NEXT, R_PREV.
  79.  *
  80.  * Returns:
  81.  *    RET_ERROR, RET_SUCCESS or RET_SPECIAL if there's no next key.
  82.  */
  83. int
  84. __bt_seq(dbp, key, data, flags)
  85.     const DB *dbp;
  86.     DBT *key, *data;
  87.     u_int flags;
  88. {
  89.     BTREE *t;
  90.     EPG e;
  91.     int status;
  92.  
  93.     t = dbp->internal;
  94.  
  95.     /* Toss any page pinned across calls. */
  96.     if (t->bt_pinned != NULL) {
  97.         mpool_put(t->bt_mp, t->bt_pinned, 0);
  98.         t->bt_pinned = NULL;
  99.     }
  100.  
  101.     /*
  102.      * If scan unitialized as yet, or starting at a specific record, set
  103.      * the scan to a specific key.  Both bt_seqset and bt_seqadv pin the
  104.      * page the cursor references if they're successful.
  105.      */
  106.     switch(flags) {
  107.     case R_NEXT:
  108.     case R_PREV:
  109.         if (ISSET(t, B_SEQINIT)) {
  110.             status = bt_seqadv(t, &e, flags);
  111.             break;
  112.         }
  113.         /* FALLTHROUGH */
  114.     case R_CURSOR:
  115.     case R_FIRST:
  116.     case R_LAST:
  117.         status = bt_seqset(t, &e, key, flags);
  118.         break;
  119.     default:
  120.         errno = EINVAL;
  121.         return (RET_ERROR);
  122.     }
  123.  
  124.     if (status == RET_SUCCESS) {
  125.         status = __bt_ret(t, &e, key, data);
  126.  
  127.         /* Update the actual cursor. */
  128.         t->bt_bcursor.pgno = e.page->pgno;
  129.         t->bt_bcursor.index = e.index;
  130.  
  131.         /*
  132.          * If the user is doing concurrent access, we copied the
  133.          * key/data, toss the page.
  134.          */
  135.         if (ISSET(t, B_DB_LOCK))
  136.               mpool_put(t->bt_mp, e.page, 0);
  137.         else
  138.             t->bt_pinned = e.page;
  139.         SET(t, B_SEQINIT);
  140.     }
  141.     return (status);
  142. }
  143.  
  144. /*
  145.  * BT_SEQSET -- Set the sequential scan to a specific key.
  146.  *
  147.  * Parameters:
  148.  *    t:    tree
  149.  *    ep:    storage for returned key
  150.  *    key:    key for initial scan position
  151.  *    flags:    R_CURSOR, R_FIRST, R_LAST, R_NEXT, R_PREV
  152.  *
  153.  * Side effects:
  154.  *    Pins the page the cursor references.
  155.  *
  156.  * Returns:
  157.  *    RET_ERROR, RET_SUCCESS or RET_SPECIAL if there's no next key.
  158.  */
  159. static int
  160. bt_seqset(t, ep, key, flags)
  161.     BTREE *t;
  162.     EPG *ep;
  163.     DBT *key;
  164.     int flags;
  165. {
  166.     EPG *e;
  167.     PAGE *h;
  168.     pgno_t pg;
  169.     int exact;
  170.  
  171.     /*
  172.      * Delete any already deleted record that we've been saving because
  173.      * the cursor pointed to it.  Since going to a specific key, should
  174.      * delete any logically deleted records so they aren't found.
  175.      */
  176.     if (ISSET(t, B_DELCRSR) && __bt_crsrdel(t, &t->bt_bcursor))
  177.         return (RET_ERROR);
  178.  
  179.     /*
  180.      * Find the first, last or specific key in the tree and point the cursor
  181.      * at it.  The cursor may not be moved until a new key has been found.
  182.      */
  183.     switch(flags) {
  184.     case R_CURSOR:                /* Keyed scan. */
  185.         /*
  186.          * Find the first instance of the key or the smallest key which
  187.          * is greater than or equal to the specified key.  If run out
  188.          * of keys, return RET_SPECIAL.
  189.          */
  190.         if (key->data == NULL || key->size == 0) {
  191.             errno = EINVAL;
  192.             return (RET_ERROR);
  193.         }
  194.         e = __bt_first(t, key, &exact);    /* Returns pinned page. */
  195.         if (e == NULL)
  196.             return (RET_ERROR);
  197.         /*
  198.          * If at the end of a page, skip any empty pages and find the
  199.          * next entry.
  200.          */
  201.         if (e->index == NEXTINDEX(e->page)) {
  202.             h = e->page;
  203.             do {
  204.                 pg = h->nextpg;
  205.                 mpool_put(t->bt_mp, h, 0);
  206.                 if (pg == P_INVALID)
  207.                     return (RET_SPECIAL);
  208.                 if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
  209.                     return (RET_ERROR);
  210.             } while (NEXTINDEX(h) == 0);
  211.             e->index = 0;
  212.             e->page = h;
  213.         }
  214.         *ep = *e;
  215.         break;
  216.     case R_FIRST:                /* First record. */
  217.     case R_NEXT:
  218.         /* Walk down the left-hand side of the tree. */
  219.         for (pg = P_ROOT;;) {
  220.             if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
  221.                 return (RET_ERROR);
  222.             if (h->flags & (P_BLEAF | P_RLEAF))
  223.                 break;
  224.             pg = GETBINTERNAL(h, 0)->pgno;
  225.             mpool_put(t->bt_mp, h, 0);
  226.         }
  227.  
  228.         /* Skip any empty pages. */
  229.         while (NEXTINDEX(h) == 0 && h->nextpg != P_INVALID) {
  230.             pg = h->nextpg;
  231.             mpool_put(t->bt_mp, h, 0);
  232.             if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
  233.                 return (RET_ERROR);
  234.         }
  235.  
  236.         if (NEXTINDEX(h) == 0) {
  237.             mpool_put(t->bt_mp, h, 0);
  238.             return (RET_SPECIAL);
  239.         }
  240.  
  241.         ep->page = h;
  242.         ep->index = 0;
  243.         break;
  244.     case R_LAST:                /* Last record. */
  245.     case R_PREV:
  246.         /* Walk down the right-hand side of the tree. */
  247.         for (pg = P_ROOT;;) {
  248.             if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
  249.                 return (RET_ERROR);
  250.             if (h->flags & (P_BLEAF | P_RLEAF))
  251.                 break;
  252.             pg = GETBINTERNAL(h, NEXTINDEX(h) - 1)->pgno;
  253.             mpool_put(t->bt_mp, h, 0);
  254.         }
  255.  
  256.         /* Skip any empty pages. */
  257.         while (NEXTINDEX(h) == 0 && h->prevpg != P_INVALID) {
  258.             pg = h->prevpg;
  259.             mpool_put(t->bt_mp, h, 0);
  260.             if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
  261.                 return (RET_ERROR);
  262.         }
  263.  
  264.         if (NEXTINDEX(h) == 0) {
  265.             mpool_put(t->bt_mp, h, 0);
  266.             return (RET_SPECIAL);
  267.         }
  268.  
  269.         ep->page = h;
  270.         ep->index = NEXTINDEX(h) - 1;
  271.         break;
  272.     }
  273.     return (RET_SUCCESS);
  274. }
  275.  
  276. /*
  277.  * BT_SEQADVANCE -- Advance the sequential scan.
  278.  *
  279.  * Parameters:
  280.  *    t:    tree
  281.  *    flags:    R_NEXT, R_PREV
  282.  *
  283.  * Side effects:
  284.  *    Pins the page the new key/data record is on.
  285.  *
  286.  * Returns:
  287.  *    RET_ERROR, RET_SUCCESS or RET_SPECIAL if there's no next key.
  288.  */
  289. static int
  290. bt_seqadv(t, e, flags)
  291.     BTREE *t;
  292.     EPG *e;
  293.     int flags;
  294. {
  295.     EPGNO *c, delc;
  296.     PAGE *h;
  297.     indx_t index;
  298.     pgno_t pg;
  299.  
  300.     /* Save the current cursor if going to delete it. */
  301.     c = &t->bt_bcursor;
  302.     if (ISSET(t, B_DELCRSR))
  303.         delc = *c;
  304.  
  305.     if ((h = mpool_get(t->bt_mp, c->pgno, 0)) == NULL)
  306.         return (RET_ERROR);
  307.  
  308.     /*
  309.       * Find the next/previous record in the tree and point the cursor at it.
  310.      * The cursor may not be moved until a new key has been found.
  311.      */
  312.     index = c->index;
  313.     switch(flags) {
  314.     case R_NEXT:            /* Next record. */
  315.         if (++index == NEXTINDEX(h)) {
  316.             do {
  317.                 pg = h->nextpg;
  318.                 mpool_put(t->bt_mp, h, 0);
  319.                 if (pg == P_INVALID)
  320.                     return (RET_SPECIAL);
  321.                 if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
  322.                     return (RET_ERROR);
  323.             } while (NEXTINDEX(h) == 0);
  324.             index = 0;
  325.         }
  326.         break;
  327.     case R_PREV:            /* Previous record. */
  328.         if (index-- == 0) {
  329.             do {
  330.                 pg = h->prevpg;
  331.                 mpool_put(t->bt_mp, h, 0);
  332.                 if (pg == P_INVALID)
  333.                     return (RET_SPECIAL);
  334.                 if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
  335.                     return (RET_ERROR);
  336.             } while (NEXTINDEX(h) == 0);
  337.             index = NEXTINDEX(h) - 1;
  338.         }
  339.         break;
  340.     }
  341.  
  342.     e->page = h;
  343.     e->index = index;
  344.  
  345.     /*
  346.      * Delete any already deleted record that we've been saving because the
  347.      * cursor pointed to it.  This could cause the new index to be shifted
  348.      * down by one if the record we're deleting is on the same page and has
  349.      * a larger index.
  350.      */
  351.     if (ISSET(t, B_DELCRSR)) {
  352.         CLR(t, B_DELCRSR);            /* Don't try twice. */
  353.         if (c->pgno == delc.pgno && c->index > delc.index)
  354.             --c->index;
  355.         if (__bt_crsrdel(t, &delc))
  356.             return (RET_ERROR);
  357.     }
  358.     return (RET_SUCCESS);
  359. }
  360.  
  361. /*
  362.  * __BT_CRSRDEL -- Delete the record referenced by the cursor.
  363.  *
  364.  * Parameters:
  365.  *    t:    tree
  366.  *
  367.  * Returns:
  368.  *    RET_ERROR, RET_SUCCESS
  369.  */
  370. int
  371. __bt_crsrdel(t, c)
  372.     BTREE *t;
  373.     EPGNO *c;
  374. {
  375.     PAGE *h;
  376.     int status;
  377.  
  378.     CLR(t, B_DELCRSR);            /* Don't try twice. */
  379.     if ((h = mpool_get(t->bt_mp, c->pgno, 0)) == NULL)
  380.         return (RET_ERROR);
  381.     status = __bt_dleaf(t, h, c->index);
  382.     mpool_put(t->bt_mp, h, MPOOL_DIRTY);
  383.     return (status);
  384. }
  385.